
var list = [1, 6, 8, 7, 5, 2, 3, 9, 4];

function bubbleSort(list) {
    let length = list.length;
    if (!length) return [];
    for (let i = 0; i < length; i++) {
        for (let j = 1; j < length - i; j++) {
            if (list[j] > list[j - 1]) {
                let temp = list[j];
                list[j] = list[j - 1];
                list[j - 1] = temp;
            }
        }
    }
    return list;
}

function selectSort(list) {
    let length = list.length;
    let index, temp;
    for (let i = 0; i < length - 1; i++) {
        index = i;
        for (let j = i + 1; j < length; j++) {
            if (list[j] < list[index]) {
                index = j;
            }
        }
        temp = list[i];
        list[i] = list[index];
        list[index] = temp;
    }
    return list;
}

function insertSort(list) {
    let length = list.length;
    let preIndex, current;
    for (let i = 1; i < length; i++) {
        preIndex = i - 1;
        current = list[i];
        while (preIndex >= 0 && list[preIndex] > current) {
            list[preIndex + 1] = list[preIndex];
            preIndex--;
        }
        list[preIndex + 1] = current;
    }
    return list;
}


function quickSort(list, left, right) {
    let length = list.length;
    left = typeof left != 'number' ? 0 : left;
    right = typeof right != 'number' ? length - 1 : right;
    if (left < right) {
        // 获取基准点,进行分区
        partitionIndex = partition(list, left, right);
        // 递归调用基准左右的子序列进行快排
        quickSort(list, left, partitionIndex - 1);
        quickSort(list, partitionIndex + 1, right);
    }
    return list;
}

function partition(arr, left, right) {
    let privot = left;
    let index = left + 1;
    for (let i = index; i <= right; i++) {
        if (arr[i] > arr[privot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, privot, index - 1);
    return index - 1;
}
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// var res = bubbleSort(list);
// var res = selectSort(list);
var res = insertSort(list);
// var res = quickSort(list);
console.log(res);